package com.origin.niuke.tree;

import general_class.TreeNode;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/28 11:15
 * 在二叉树中找到两个节点的最近公共祖先
 * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 * 算法：树 + 深度优先搜索 | 广度优先搜索
 * 当 root == null || root.val == o1 || root.val == o2 时，直接返回 root
 * 否则，分别去 root 的左子树和右子树中去查找，相当于前序遍历
 * 1、如果左子树和右子树中都有值，表示 o1 和 o2 分别在 root 的两侧，那么 root 就是结果
 * 2、如果左子树和右子树中都没有值，表示 root 中没有 o1 和 o2
 * 3、如果左子树没有值，表示 o1 和 o2 在右子树中；反之，在左子树中
 */
public class NC102 {

    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        return lcaRecursion(root, o1, o2).val;
    }

    TreeNode lcaRecursion(TreeNode root, int o1, int o2) {
        if (root == null) return root;
        if (root.val == o1 || root.val == o2) return root;
        TreeNode left = lcaRecursion(root.left, o1, o2);
        TreeNode right = lcaRecursion(root.right, o1, o2);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }

    /**
     * 广度优先搜索
     * 存储每个节点的父节点
     * 看 o1 和 o2 的父节点有没有交集
     */
    int lcaIterate(TreeNode root, int o1, int o2) {
        Map<Integer, Integer> parent = new HashMap<>();
        parent.put(root.val, root.val);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
            TreeNode poll = queue.poll();
            if (poll.left != null) {
                parent.put(poll.left.val, poll.val);
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                parent.put(poll.right.val, poll.val);
                queue.offer(poll.right);
            }
        }
        Set<Integer> set = new HashSet<>();
        while (o1 != root.val) {
            set.add(o1);
            o1 = parent.get(o1);
        }
        while (o2 != root.val) {
            if (set.contains(o2)) return o2;
            o2 = parent.get(o2);
        }
        return o2;
    }

}
